package com.liunian.algorithmstudy.tree;

public class ConstructMaximumBinaryTree654 extends TreeNode {

	// 方法一
	public TreeNode constructMaximumBinaryTree(int[] nums) {
		if (nums.length == 0) {
			return null;
		}
		int[] preprocess = getMaxValue(nums);
		TreeNode root = new TreeNode(preprocess[1]);
		int[] leftNums = processNums(nums, 0, preprocess[0]);
		int[] rightNums = processNums(nums, preprocess[0] + 1, nums.length);
		TreeNode leftTree = constructMaximumBinaryTree(leftNums);
		TreeNode rightTree = constructMaximumBinaryTree(rightNums);
		root.left = leftTree;
		root.right = rightTree;
		return root;
	}

	private int[] getMaxValue(int[] nums) {
		int index = 0;
		int maxValue = nums[0];
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > maxValue) {
				index = i;
				maxValue = nums[i];
			}
		}
		return new int[] {index, maxValue};
	}

	private int[] processNums(int[] nums, int from, int to) {
		int[] res = new int[to - from];
		for (int i = 0; i < to - from; i++) {
			res[i] = nums[i + from];
		}
		return res;
	}

	// 方法二
	public TreeNode constructMaximumBinaryTree4(int[] nums) {
		return constructMaximumBinaryTree5(nums, 0, nums.length - 1);
	}

	private TreeNode constructMaximumBinaryTree5(int[] nums, int leftIndex, int rightIndex) {
		if (rightIndex - leftIndex < 0) {
			return null;
		}
		if (rightIndex - leftIndex == 0) {
			return new TreeNode(nums[leftIndex]);
		}
		int maxValue = nums[leftIndex];
		int index = leftIndex;
		for (int i = leftIndex + 1; i <= rightIndex; i++) {
			if (nums[i] > maxValue) {
				maxValue = nums[i];
				index = i;
			}
		}
		TreeNode root = new TreeNode(maxValue);
		root.left = constructMaximumBinaryTree5(nums, leftIndex, index - 1);
		root.right = constructMaximumBinaryTree5(nums, index + 1, rightIndex);
		return root;
	}


}
